package offer;

public class offerII_0051 {
    public int maxPathSum(TreeNode root) {
        int[] max=new int[1];
        max[0]=Integer.MIN_VALUE;
        maxsum(root,max);
        return max[0];
    }
    public int maxsum(TreeNode node,int[] max){
        if(node==null) return 0;
        int left=maxsum(node.left,max);
        int right=maxsum(node.right,max);
        if(left<0&&right<0){
            max[0]=Math.max(max[0], node.val);
            return node.val;
        }
        else if(left<0){
            max[0]=Math.max(max[0], node.val+right);
            return node.val+right;
        }
        else if(right<0){
            max[0]=Math.max(max[0], node.val+left);
            return node.val+left;
        }
        else{
            max[0]=Math.max(max[0], node.val+Math.max(left,right));
            max[0]=Math.max(max[0],node.val+left+right);
            return node.val+Math.max(left,right);
        }
    }
}
